package me.mingshan.leetcode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author hanjuntao
 * @date 2025/8/23 0023
 */
public class L_146_LRU缓存 {
    private final Map<Integer, Integer> map;
    private final LinkedList<Integer> queue;

    private final int capacity;

    public L_146_LRU缓存(int capacity) {
        map = new HashMap<>();
        queue = new LinkedList<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            int value = map.get(key);
            moveToHead(key);
            return value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (!map.containsKey(key)) {
            queue.addFirst(key);
        } else {
            moveToHead(key);
        }

        map.put(key, value);

        // 如果不存在，首先判断队列中是否已经满了
        if (queue.size() > capacity) {
            // 移除队列中最后一个结点
            map.remove(queue.removeLast());
        }
    }

    private void moveToHead(int key) {
        queue.remove(Integer.valueOf(key));
        queue.addFirst(key);
    }
}
